import collections
from typing import List


class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph_in = collections.defaultdict(set)
        graph_out = collections.defaultdict(set)
        for edge in relations:
            graph_in[edge[1]].add(edge[0])
            graph_out[edge[0]].add(edge[1])

        count = {}  # 节点入射边统计
        queue = collections.deque()  # 当前入射边为0的节点列表

        # 统计所有节点的入射边
        for node in graph_in:
            count[node] = len(graph_in[node])
        for i in range(1, n + 1):
            if i not in count:
                count[i] = 0
                queue.append(i)

        if len(queue) == 0:
            return -1

        # 拓扑排序
        ans = 0
        order = []
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                order.append(node)
                for next in graph_out[node]:
                    count[next] -= 1
                    if count[next] == 0:
                        queue.append(next)
            ans += 1

        if len(order) == n:
            return ans
        else:
            return -1


if __name__ == "__main__":
    print(Solution().minimumSemesters(n=3, relations=[[1, 3], [2, 3]]))  # 2
    print(Solution().minimumSemesters(n=3, relations=[[1, 2], [2, 3], [3, 1]]))  # -1

    # 测试用例32/39
    print(Solution().minimumSemesters(n=5, relations=[[1, 2], [3, 4], [4, 5], [5, 2]]))  # 4
